\section{M\'etodos}
\label{metodos}

% Que quiero lograr
Nuesto m\'etodo har\'a la asumpci\'on base de que una reacci\'on captura la sem\'antica de la instucci\'on que la caus\'o. Por lo tanto, si dos frases resultan en la misma reacci\'on, son {\em parafrases} entre s\'i, y frases similares deber\'ian generar la misma reacci\'on. Este enfoque nos permite predecir reacciones para instrucciones no vistas previamente.

En orden de alcanzar los goles propuestos, pretendemos dividir nuestro trabajo en dos \'areas. La primera fase se encargar\'a de la anotaci\'on autom\'atica del corpora, asociando instrucciones y reacciones como resultado de una relaci\'on causa-consecuencia. La segunda fase se enfocar\'a en la interpretaci\'on de nuevas instrucciones, prediciendo una respuesta apropiada para una nueva instrucci\'on de acuerdo a reacciones previas observadas en el corpora.

\subsection{Fase de Anotaci\'on}
La principal dificultad en aprender de grandes cantidades de datos f\'aciles de recolectar es anotar autom\'aticamente un corpus no anotado. Nuestro primer enfoque al m\'etodo de anotaci\'on consistir\'a de dos partes: primero, {\em segmentar} una traza de interacci\'on de bajo nivel en frases y reacciones correspondientes; segundo, {\em discretizar} esas reacciones en secuencias de acciones can\'onicas.

Dado que los usuarios pueden moverse libremente mientras interact\'uan con un mundo virtual, sus acciones conforman un flujo de comportamiento cont\'inuo. La {\em segmentaci\'on} de este flujo nos permite asociar instrucciones y reacciones, dado que consideramos que cualquier acci\'on del usuario luego de una instrucci\'on es una respuesta directa a \'esta. Este m\'etodo, sin embargo, puede ser enga\~nado f\'acilmente al considerar movimientos superfluos como parte de la reacci\'on esperada, lo cual explica por qu\'e la {\em discretizaci\'on} es requerida: una estrategia apropiada de discretizaci\'on deber\'ia eliminar los comportamientos irrelevantes al objetivo de la tarea.

Consideremos el siguiente ejemplo: nuestro agente se encuentra frente a una puerta cerrada. Nuestra primera instrucci\'on, {\em ``haz click en el bot\'on para abrir la puerta''}, lleva al agente a caminar por toda la habitaci\'on hasta que encuentra el switch y lo presiona. Luego gira y atraviesa la puerta. Nuestra siguiente instrucci\'on, {\em ``toma la primera puerta a tu derecha''}, es seguida pro el agente caminando hasta la puerta correcta y atraves\'andola. En la etapa de {\em segmentaci\'on} asociamos todas las acciones realizadas entre la pronunciaci\'on de la primera instrucci\'on y la segunca con la primera instrucci\'on, y las acciones restantes con la segunda instrucci\'on. Luego, en la {\em etapa de discretizaci\'on}, generamos una secuencia de acciones (en particular, la secuencia {\em m\'as corta}) tal que cambia el estado del mundo en la misma forma que lo hizo el agente. Los resultados de tal discretizaci\'on se muestran en la Figura~\ref{fig:discretization}a), 

\begin{figure}
\begin{minipage}{0.3\textwidth}
{\tt haz click en el bot\'on para abrir la puerta}\\
{\em [camina hasta el bot\'on]}\\
{\em [presiona el bot\'on]}\\
{\em [atraviesa la puerta]}\\
\\
{\tt toma la primera puerta a tu derecha}\\
{\em [camina hasta la primera puerta]}\\
{\em [atraviesa la puerta]}
\begin{center}a)\end{center}
\end{minipage}
\hspace*{0.03\textwidth}
\begin{minipage}{0.3\textwidth}
{\tt haz click en el bot\'on para abrir la puerta}\\
\textbf{{\em [camina hasta el bot\'on]}}\\
\textbf{{\em [presiona el bot\'on]}}\\
\textbf{{\em [atraviesa la puerta]}}\\
\\
{\tt toma la primera puerta a tu derecha}\\
\textbf{{\em [camina hasta la primera puerta]}}\\
\textbf{{\em [atraviesa la puerta]}}
\begin{center}b)\end{center}
\end{minipage}
\hspace*{0.03\textwidth}
\begin{minipage}{0.3\textwidth}
{\tt haz click en el bot\'on para abrir la puerta}\\
\textbf{{\em [camina hasta el bot\'on]}}\\
{\em [presiona el bot\'on]}\\
{\em [atraviesa la puerta]}\\
\\
{\tt toma la primera puerta a tu derecha}\\
\textbf{{\em [camina hasta la primera puerta]}}\\
{\em [atraviesa la puerta]}

\begin{center}c)\end{center}
\end{minipage}


\caption{a) Secuencia discretizada de acciones, b) Segmentaci\'on basada en comportamiento, c) Segmentaci\'on basada en visibilidad}
\label{fig:discretization}
\end{figure}


%It is important to note that, even with this simple annotation strategy, it is not clear what should be considered exactly as the {\em correct} reaction, which is why we intend to experiment with two alternate definitions: A strict definition that considers the maximum reaction according to the user's {\em behaviour}, and a loose definition based on the empyrical observation that, in situated interaction, most instructions are constrained by the current {\em visually} perceived affordances~\cite{Gibson79,Stoia06}. The first definition will be called {\em behaviour segmentation} (Bhv), and the second one will be named {\em visibility segmentation} (Vis).
%
%For the Bhv method, we'll define the reaction to an instruction as the sequence of (discretized) actions performed by the user immediately after receiving an instruction and immediately before receiving the next instruction. The Vis method, however, will be restricted to the first action performed by the user after receiving an instruction.


% Augmented definition, according to Alex's comments. There is a chance this is *longer* but not *clearer*, though. In my defense, I plea insanity.
Para la fase de anotaci\'on, no est\'a claro cu\'ales acciones discretizadas son una respuesta directa a la instrucci\'on y cu\'ales son extra: si el usuario reacciona a la instrucci\'on {\em ``busca el bot\'on verde''} girando a la derecha, encontrando el bot\'on y clickeandolo, ¿deber\'ia ser ``clickear el bot\'on'' considerado como una respuesta apropiada para la frase? ¿Es correcto reaccionar siempre ante esta instrucci\'on girando a la derecha? Dado que no tenemos una respuesta simple y clara, pretendemos experimentar con dos enfoques alternativos para definir correctamente qu\'e deber\'ia ser considerada una {\em reacci\'on can\'onica} a una instrucci\'on dada. Dada una secuencia de acciones luego de una instrucci\'on, nuestra primera definici\'on considerar\'a la reacci\'on m\'axima de acuerdo al {\em comportamiento} del usuario  -- es decir, la secuencia de acciones ser\'a considerada como una reacci\'on can\'onica. La Figura~\ref{fig:discretization}b) muestra c\'omo los ejemplos deber\'ian ser anotados en estos casos. Nuestra segunda definici\'on se basar\'a en la observaci\'on emp\'irica de que, en interacciones situadas, la mayor\'ia de las instrucciones son limitadas a los elementos {\em visibles}~\cite{Gibson79,Stoia06}, as\'i que solamente la primera acci\'on de la secuencia ser\'a considerada, y las restantes se descartan, como lo muestra la Figura~\ref{fig:discretization}c). La primera definici\'on se llamar\'a {\em Segmentaci\'on por comportamiento} (Bhv), y la segunda se llamar\'a {\em Segmentaci\'on por visibilidad} (Vis).

Finalmente, sobre el m\'etodo de discretizaci\'on, nuestro algoritmo har\'a uso de un {planner autom\'atico} y una {\em representaci\'on de plan} para la tarea, dado que esta combinaci\'on remueve exitosamente las acciones superfluas: al ajustar un plan a trav\'es de los estados iniciales y finales del usuario, obtenemos (de forma repetible y predecible) la m\'inima secuencia de acciones que llevan de un estado al otro. Nuestra representaci\'on incluir\'a: (1) el objetivo de la tarea, (2) las acciones que pueden realizarse en el ambiente, y (3) el estado actual del ambiente interactivo. Usando esta representaci\'on, el planner puede calcular un camino \'optimo entre los estados iniciales y finales de la reacci\'on, eliminando las acciones innecesarias. Si bien en un primer acercamiento planeamos utilizar el planner cl\'asico FF~\cite{Hoffmann03}, nuestra t\'ecnica puede tambi\'en trabajar con cualquier otro enfoque de planning.

\subsection{Fase de Interpretaci\'on}
Una alternativa que hemos explorado previamente para la fase de anotaci\'on, y una que consideramos para el trabajo actual, resulta en una colecci\'on de pares {\em (instrucci\'on, reacci\'on)}. La fase de interpretaci\'on usa estos pares para interpretar nuevas frases en tres pasos. Primero, filtramos el conjunto de pares, manteniendo \'unicamente aquellos cuyas reacciones pueden ejecutarse directamente desde la posici\'on actual. Segundo, agrupamos estos pares seg\'un sus reacciones. Tercero, {\em seleccionamos} el grupo con frases m\'as similares a la nueva instrucci\'on, y seleccionamos la reacci\'on de ese grupo.

El tercer paso fue tratado como un problema de clasificaci\'on, y planeamos enfocarnos con distintos m\'etodos de clasificaci\'on. El primer m\'etodo usa clasificaci\'on {\em nearest-neighbour} con tr\'es m\'etricas similares: los coeficientes de Jaccard y Overlap (midiendo el grado de solapamiento entre dos conjuntos, difiriendo \'unicamente en la normalizaci\'on del valor final~\cite{Nikravesh:2005:Overlap}), y la Distancia de Levenshtein (una m\'etrica sobre cadenas para medir la cantidad de diferencias entre ambas secuencias~\cite{levelshtein-66-binary}). El segundo m\\etodo de clasificaci\'on emple\'o una estrategia en la que consideramos cada grupo de frases como un conjunto de posibles traducciones autom\'aticas de nuestra instrucci\'on, utilizando la medida BLEU~\cite{Papineni:2002:BLEU} para seleccionar cu\'al grupo deber\'ia ser considerada la mejor traducci\'on de nuestra instrucci\'on. Finalmente, hemos entrenado tambi\'en clasificadores SVM~\cite{Cortes95} usando los unigramas de cada parafrase y la posici\'on actual del usuario como caracter\'isticas, y seleccionando su grupo como la clase de salida~\cite{CC01a}.

\subsection{Correcciones de usuarios}
Si el sistema malinterpreta una instrucci\'on, es importante tener un mecanismo para correcciones. Si bien no requerimos un mecanismo avanzado para detectar errores (debido al hecho de que, en una tarea colaborativa entre dos usuarios, el que da las instrucciones deber\'ia ser quien marque los errores), necesitamos una estrategia robusta para seleccionar la correcci\'on m\'as apropiada. Un primer acercamiento simple ser\'ia analizar la nueva frase dada por el usuario y utilizarla para seleccionar una de las acciones disponibles desde la posici\'on actual (es decir, las mismas que antes, pero eliminando la instrucci\'on que ya sabemos es err\'onea). Sin embargo, podemos obtener mejores resultados implementando un sistema m\'as robusto, en el cual analizamos la nueva instrucci\'on en el contexto de tanto sus caracter\'isticas como de los resultados previos de clasificaci\'on, corriendo nuestro proceso de predicci\'on sobre la nueva frase independientemente y luego combinando estos resultados con aquellos obtenidos en la clasificaci\'on previa.

Tomemos, por ejemplo, el caso en el que un agente reacciona a la instrucci\'on {\em ``presiona el bot\'on verde''} presionando un bot\'on rojo, pero luego de recibir la segunda instrucci\'on {\em ``no, el otro''} presiona el correcto. Si bien un enfoque simple ser\'ia utilizar \'unicamente la segunda instrucci\'on para realizar la acci\'on correcta (siguiendo un proceso deductivo de ``dado que hay dos elementos posibles, y la oraci\'on hace referencia a otro elemento, entonces presionar el bot\'on m\'as lejano es la acci\'on m\'as probable''), al detectar que una corracci\'on tiene lugar podemos mejorar nuestras posibilidades, por ejemplo, sopesando nuestra hip\'otesis actual con informaci\'on de la deducci\'on previa (dado que sabemos que nuestra interpretaci\'on m\'as probable era err\'onea, tal vez nuestra segunda opci\'on sea la correcta). Este acercamiento es particularmente \'util frente a correcciones como {\em ``no''} o {\em ``error''}, debido al hecho de que instrucciones como esta proveen poca o ninguna informaci\'on acerca del resultado esperado y ser\'ia muy dif\'icil interpretar correctamente sin hacer uso de informaci\'on previa.

% Estrategias
\subsection{Estrategias de Investigaci\'on}
Para aplicar estas t\'ecnicas y evaluarlas, necesitamos un extenso corpus. En las primeras etapas, utilizaremos el corpus recolectado en la tarea compartida de generaci\'on de lenguaje natural conocida como el GIVE Challenge~\cite{KolStrGarByrCasDalMooObe10}. Este corpus puede dividirse en dos: el primer, al cual llamamos $C_m$~\cite{GarGarKolStr10},contiene instrucciones tanto dada como obedecidas por m\'ultiples personas; el segundo, llamado $C_s$ ~\cite{benotti-denis:2011:ENLG}, fue recolectado usando m\'ultiples seguidores pero una \'unica persona dando las instrucciones. Este corpora totaliza 5580 instrucciones en un total de 14:26 hs. de interacci\'on.

Aunque este corpora es extenso, es enteramente posible que necesitemos datos extra. En este caso, planeamos recolectar primero en peque\~na escala reclutando voluntarios, y en una escala mayor (si fuera necesario) a trav\'es de internet. Servicios de {\em crowdsourcing} como Amazon Mechanical Turk, ser\'an de gran utilidad. Estas estrategias tambi\'en esperamos sean usadas en el futuro proyecto de investigaci\'on SFB 632 de Alexander Koller, por lo que datos de este corpora deber\'ian tambi\'en estar disponibles para nuestro proyecto.